#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/09/21
# @Author   :Changshu
# @File     :practice_141.py

class ListNode:
	def __init__(self,x):
		self.val=x
		self.next=None

'''使用hash
def hasCycle(head:ListNode)->bool:
	p=head
	d={}
	while p:
		if p in d:
			return True
		d[p]=1
		p=p.next
	return False
'''



'''使用快慢指针，快指针比慢指针快一步'''
def hasCycle(head:ListNode)->bool:
	if head is None or head.next is None:
		return False
	slow=head
	fast=head.next
	while slow is not fast:
		if fast is None or fast.next is None:
			return False
		slow=slow.next
		fast=fast.next.next
	return True

if __name__ == '__main__':
	head = ListNode(3)
	head.next = ListNode(2)
	head.next.next = ListNode(0)
	head.next.next.next = ListNode(-4)
	head.next.next.next.next = head.next

	b=hasCycle(head)
	print(b)